The present invention relates to communication systems and methods, and more particularly to systems and methods for providing primary and secondary data signals.
Digital communication systems can enable the exchange of bit-encoded information among various electronic devices or nodes. The functions used to accomplish this purpose can be divided into seven groups, each group corresponding to one of the layers of a seven-layer data-communications protocol model adopted by the international standards community, as described in Section 3.1 of Data Networks by Bertsekas and Gallagher (Prentice-Hall, 1987).
The lowest layer of this model, known as the physical layer, encompasses methods and apparatus used to move bits from a source to a destination. These methods and apparatus can include transmission wires, connectors, and antennas; modulators and demodulators; and the associated electronics and components used to communicate a bit stream between adjacent nodes in a communication network by means of fiber optics, coaxial cables, parallel conductor transmission lines, wireless radio links, or combinations thereof. In this context, the resulting bitstream can be referred to as a physical channel.
Once a physical channel is established and a bitstream can be communicated between network nodes, the bits provided by the bitstream can be organized for the benefit of a user or a plurality of users, thereby providing these users with logical channels derived from the raw bit-moving capacity of the physical channel. The functions used to accomplish this organization are generally encompassed by the higher layers of the seven-layer protocol model mentioned above.
For example, the North American telephone network includes a transmission method and format known as T1-rate service. This service moves bits between network nodes at the rate of 1.536 million bits per second (Mbps). In one use, the full capacity of the T1 physical channel can be employed to provide a single broadband channel for the benefit of a single user, for example, to connect a first high-capacity computer server in a first city to a second high-capacity server in a second city. In a different situation, the capacity of the T1-rate physical channel can be subdivided by multiplexing to provide twenty-four channels each having a transmission capacity of 64,000 bits per second (64 Kbps). Through functions encompassed by the higher layers of the protocol model, each of these 64 Kbps channels can be configured to support a different digital conversation or application, thereby subdividing the physical channel into a plurality of logical channels.
Error-detection techniques may be used to provide some degree of protection against transmission errors. Such errors may arise from the coupling of external disturbances (noise) into the physical channel, and may have the undesired effect of altering the logical state of bits transmitted on the physical channel, thereby altering the logical state of bits delivered by one or more of the logical channels. Error-detection may be provided by data-link-control (DLC) functions encompassed by the higher layers of the protocol model.
Under the operation of a standard DLC, a plurality of bits to be communicated can be collected and grouped into a data packet (or data signal). A packet header appended to the beginning of the frame may include flag, address, and control fields used to enable and assist the operation of other network functions. A packet trailer appended to the end of the frame may include flag bits and error-detection code bits (parity bits). Together, the header, packet, and trailer can be referred to as a frame. The purpose of the error-detection code bits included in the frame is to provide a means of detecting the presence of bit errors introduced into the frame during its transit across the physical channel.
One particular method of generating and processing error-detection code bits is the cyclic redundancy check (CRC), the operation of which can be described as a series of multiplication and division operations among polynomials having modulo-2 coefficients in recognition of their representation of digital bits. In this representation, the contents of a partial frame (i.e., the frame excluding its header flag and its trailer) can be thought of as an N-degree polynomial, where N is the number of bits in the partial frame. This polynomial is divided by a second polynomial known as the CRC generator polynomial. On completion of the division, the resulting remainder is incorporated into the packet trailer as the error-detection code bits, and the frame is passed to the physical channel for transmission.
Upon receipt of the frame, the receiving node again computes the polynomial division of the received bits, and compares the resulting remainder with the received remainder. Transmission errors are indicated by any disagreement between the remainder as conveyed by the received frame and the remainder as re-computed by the receiver.
The polynomial model as well as the limitations and capabilities inherent in CRCs derived from various generator polynomials in commercial use are described more fully by Boudreau, Bergman, and Irvin, in xe2x80x9cPerformance Of A Cyclic Redundancy Check And Its Interaction With A Data Scramblerxe2x80x9d (IBM Journal of Research and Development, Vol. 38, No. 6, November 1994, pp. 651-658). From mathematical results laid out in this paper, it can be shown that current error-detection schemes may provide excess error-detection capacity.
Excess error-detection capacity may arise from practical design constraints. For example, the number of error-detection code bits provided by a commercially useful CRC may have a granularity based on an integral multiple of eight, due to the byte-oriented nature of conventional digital communication apparatus. Moreover, in commercial usage, most useful CRC generator polynomials are chosen from a relatively small set of accepted industry standards that provide either eight, sixteen, or thirty-two error-detection code bits. For this reason, a system architect may select a 32-bit CRC to provide an abundance of capacity relative to the task at hand, rather than select a 16-bit CRC which might provide insufficient error-detection capacity. The inflexibility of this granularity may thus lead to a wasteful excess of error-detection capacity.
In addition, one link of a communications channel may require a higher level of error-detection than another link. In a cellular radiotelephone communications system, for example, a frame of data may be transmitted from a first mobile terminal to a first base station over a first radio link, from the first base station to a second base station over one or more wired links, and from the second base station to a second mobile terminal over a second radio link wherein the radio links provide a less reliable transmission medium than the wired links between the two base stations. A single error-detection code, such as a CRC code, can thus be used for a frame transmitted over the different links to provide a level of error-detection sufficient to accommodate the less reliable radio links. This level of error-detection, however, may provide excess error-detection capacity with respect to the wired links.
Excess error-detection capacity may have important commercial considerations that follow from the nature of the DLC of which the error-detection is part. In addition to its error-detection functions, the DLC may control access to the physical transmission medium, and, in this sense, may impose a logical channel upon the physical channel. In doing so, the DLC may also impose limits inherent in its predetermined frame structure, and, in particular, may constrain transmission efficiency over more reliable links by requiring excess error-detection capacity in its format.
The DLC""s use of excess error-detection capacity may have adverse economic consequences to the end-user of the communication system. If the end-user has a need for a small amount of additional transmission capacity, for example, to implement a secondary channel for the purpose of carrying network-management information or for extending the reach of an exhausted control field, that user may be required to procure additional physical-channel bandwidth from a common carrier. This procurement may incur a penalty in complexity and in operating cost. Such problems may become particularly acute when the physical channel is provided by a wireless communication network, such as a cellular or satellite network, where the limitations imposed by regulatory agencies to conserve the finite electromagnetic spectrum may make the purchase of additional transmission capacity prohibitively expensive.
Thus, there is a need to enable the DLC to recapture excess error-detection capacity and apply this recaptured capacity toward providing a secondary logical channel over which the end-user or the common carrier itself may communicate incidental information without increasing the bandwidth needed to accommodate the physical channel. In this way, spectral resources in a wireless communication system may be conserved, and wasteful expenditures may be reduced in a wireline communication system.
A method for combining information from two sources using excess error-detection capacity and for separating the combined information after transmission over one physical channel is discussed, for example, in U.S. Pat. No. 5,862,160 to David R. Irvin et al. entitled xe2x80x9cSecondary Channel For Communication Networksxe2x80x9d. The Irvin et al. ""160 patent is assigned to the assignee of the present application, and shares a common inventor with the present application. In addition, the disclosure of the Irvin et al. patent is incorporated herein in its entirety by reference.
In the Irvin et al. ""160 patent, a specified data mask which represents a specified data input pattern is exclusively ORed (XORed) with a data stream including an error-detection code before transmission to induce an error-detection code violation. At the receiving end, if the calculated and received error-detection code bits differ, at least one specified mask is XORed with the received data stream. In general, the receiving system contains a list of masks that are the same as those which are in the transmitting system. The received error-detection code bits are again compared to the calculated error-detection code bits for the XORed product of the data frame and mask (XOR product).
The process is repeated for every specified mask stored within the receiver. If the received error-detection code bits differ from the computed error-detection code bits, the receiving system assumes that a transmission error has occurred. If the received error-detection code bits agree with the computed error-detection code bits, then the receiving system concludes that the input data frame has been recreated. The reason for this conclusion is that the XORed product of the data frame and the mask is the original data frame. Moreover, the mask used to recreate the original data frame is the same as the mask used at the transmission end of the communication link.
The method from the disclosure of the Irvin et al. ""160 patent, however, may be unable to decode either the original data frame or data originated from the second source if a transmission/reception error occurs.
It is therefore an object of the present invention to provide improved methods and systems that encode a second data signal on a frame of bits including a first data signal.
It is another object of the present invention to provide methods and systems that encode a second data signal on a frame of bits including a first data signal wherein the first and second data signals can be received if errors occur during transmission.
These and other objects may be provided according to the present invention by including an error-correcting code in the frame of bits wherein the error-correcting code has a capacity to detect and correct a greater number of bit errors than are expected to be induced during transmission/reception over a communications channel. The excess error correcting capacity can thus be used to encode a second data signal on the frame of bits including the first data signal and the error-correcting code so that the first and second data signals can be successfully received even when an error is induced during transmission/reception.
In particular, a method according to the present invention can include providing a frame of bits including a first plurality of bits defining the first data signal and a second plurality of bits defining an error-correcting code having capacity to correct N bit errors in the frame, and associating at least one bit position but less than N bit positions of the frame with a message type of the second data signal. The associated bit positions of the frame are inverted to encode the message type in the frame of bits, and the encoded frame of bits is transmitted. The method can also include receiving the encoded frame of bits, and performing error correction on the received encoded frame of bits using the error-correcting code to decode the associated bit positions to recreate the first plurality of bits defining the first data signal. The message type can also be determined based on the decoded associated bit positions to receive the second data signal including the message type.
Moreover, the step of associating can include associating a plurality of combinations of at least one bit position with a respective plurality of message types of the second data signal. One of the plurality of associated combinations of at least one bit position representing one of the message types can be selected, and the step of inverting the associated bit positions can include inverting the selected associated combination of at least one bit position. For example, four message types can be provided such that message type 0 represents the bit combination xe2x80x9c00xe2x80x9d, the message type 1 represents the bit combination xe2x80x9c01xe2x80x9d, the message type 2 represents the bit combination xe2x80x9c10xe2x80x9d, and the message type 3 represents the bit combination xe2x80x9c11xe2x80x9d. Furthermore, a frame of bits can include 100 bits such that bit positions 75 and 80 are associated with message type 0 (xe2x80x9c00xe2x80x9d), bit positions 76 and 81 are associated with message type 1 (xe2x80x9c01xe2x80x9d), bit positions 77 and 82 are associated with message type 2 (xe2x80x9c10xe2x80x9d), and bit positions 78 and 83 are associated with message type 3 (xe2x80x9c11xe2x80x9d).
According to this example, message type 0 can be transmitted by inverting bit positions 75 and 80, message type 1 can be transmitted by inverting frame bit positions 76 and 81, message type 2 can be transmitted by inverting frame bit positions 77 and 82, and message type 3 can be transmitted by inverting frame bit positions 78 and 83. After receiving the encoded frame of bits including the inverted associated bit positions, error correction using the error-correcting code can be performed to decode the bit positions associated with the transmitted message type and to recreate the frame of bits as it existed prior to inverting the bit positions associated with the message type thereby recreating the first data signal. The step of performing error correction can also be used to determine the message type associated with the inverted bits to receive the second data signal.
In addition, the step of transmitting the encoded frame of bits can include transmitting the encoded frame of bits over a wired communications link, and the step of receiving the encoded frame of bits can include receiving the encoded frame of bits over the wired communications link. Moreover, the step of providing the frame of bits can include receiving the frame of bits at the first node over a wireless communication link, and the step of transmitting the encoded frame of bits can include transmitting the encoded frame of bits over a wired communications link. The error correcting code can thus be selected to provide an acceptable level of error-correcting capacity with respect to a bit error rate expected over the wireless communications link, and to provide an excess error-correcting capacity with respect to a lower bit error rate expected over the wired communication link.
The step of associating at least one bit position but less than N bit positions of the frame with a message type can include associating a plurality of spaced apart bit positions with the message type. A larger number of bit positions associated with a message type reduces the possibility that a random bit error incurred during transmission/reception can be misinterpreted as the message type. By spacing apart bit positions associated with a message type, the likelihood that a burst error occurring over the communications channel is misinterpreted as the message type can be reduced.
A method according to the present invention can also include determining a bit error rate for the communications channel and suppressing transmission of the second data signal when the determined bit error rate exceeds a predetermined threshold. In particular, a forward bit error rate (BER) can be determined for information received at the second node from the first node, and transmission of the second data signal can be suppressed from the first node to the second node when the bit error rate exceeds a predetermined threshold. The full error-correcting capacity of the error-correcting code can be used to correct transmission/reception errors incurred over a communications channel by suppressing forward transmission of the second data signal.
Alternately, it may be relatively accurate to assume symmetrical forward and reverse bit error rates when determining whether to suppress transmission of the second data signal. A method according to the present invention can thus include determining a bit error rate (BER) for information received at the first node from the second node, and suppressing transmission of the second data signal from the first node to the second node when the bit error rate exceeds a predetermined threshold. Accordingly, decisions regarding suppressing transmission of the second data signal can be made at the first node without knowledge of bit error rates determined at the second node.
Because methods according to the present invention rely on excess capacity of an error-correcting code to encode the second data signal, bit errors incurred during transmission/reception over a communications channel can be corrected while receiving both the first and second data signals. In particular, the step of receiving the frame of bits can include receiving the frame of bits with the intentionally inverted associated bit positions and with an additional unintentionally inverted bit position (such as a transmission/reception error incurred over a communications channel), and the step of performing error correction can further include correcting the additional unintentionally inverted bit position.
Methods and systems according to the present invention can thus allow encoding a second data signal on a frame of bits including a first data signal and an error-correcting code using excess capacity of the error correcting code. Methods and systems according to the present invention can also provide reception of both the first and second data signals even if a bit error is incurred during transmission/reception over a communications channel.